#k[1],k[2],...,k[n] stores in p[0],p[1],...,p[n-1]
#d[0],d[2],...,d[n] stores in q[0],q[1],...,q[n]

def optimal_bst(p,q):
    n=len(p)
    e={}
    w={}
    root={}
    for i in xrange(1,n+2):
        e[i,i-1]=q[i-1]
        w[i,i-1]=q[i-1]
    for l in xrange(1,n+1):
        for i in xrange(1,n-l+2):
            j=i+l-1
            w[i,j]=w[i,j-1]+p[j-1]+q[j]
            for r in xrange(i,j+1):
                t=e[i,r-1]+e[r+1,j]+w[i,j]
                if (i,j) not in e or t<e[i,j]:
                    e[i,j]=t
                    root[i,j]=r
    return e,root
def print_root(root,n):
    for l in range(n,0,-1):
        for i in range(1,n-l+2):
            j=i+l-1
            print root[i,j],
        print
def construct_optimal_bst(root,i,j,parent):
    if j==i-1:
        print 'd',j,
        if j<parent:
            print 'left child of', parent
        else:
            print 'right child of', parent
        return
    r=root[i,j]
    print 'k',r,
    if parent is None:
        print 'is the root'
    elif r<parent:
        print 'is left child of', parent
    else:
        print 'is right child of', parent
    construct_optimal_bst(root,i,r-1,r)
    construct_optimal_bst(root,r+1,j,r)

if __name__=='__main__':
    p=[0.15,0.1,0.05,0.1,0.2]
    q=[0.05,0.1,0.05,0.05,0.05,0.1]
    e,root=optimal_bst(p,q)
    #print_root(root,len(p))
    construct_optimal_bst(root,1,5,None)
